package com.s4.queue;

/**
 * 循环队列
 */
public class CircleQueue implements IQueue {

	protected static final int DEFAULT_LENGTH = 10;

	protected final Object[] datas;

	// head表示队头下标，tail表示队尾下标
	protected int head = 0;
	protected int tail = head;

	public CircleQueue() {
		this(DEFAULT_LENGTH);
	}

	public CircleQueue(int length) {
		this.datas = new Object[length];
	}

	/**
	 * 数组已用长度
	 */
	@Override
	public int getLength() {
		return (this.tail - this.head + this.getPresetLength())
				% this.getPresetLength();
	}

	@Override
	public int getPresetLength() {
		return this.datas.length;
	}

	/*
	 * 入队
	 */
	@Override
	public boolean enqueue(Object value) {
		if (this.isFull()) {
			return false;
		}
		this.datas[this.tail] = value;
		this.tail = indexPlus(this.tail);
		return true;
	}

	private int indexPlus(int index) {
		return this.fixedIndex(index + 1);
	}

	private int fixedIndex(int index) {
		return index % this.getPresetLength();
	}

	@Override
	public boolean isEmpty() {
		return this.head == this.tail;
	}

	@Override
	public boolean isFull() {
		// 当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。
		return (this.tail + 1) % this.getPresetLength() == this.head;
	}

	/*
	 * 出队，复杂度是 O(1)
	 */
	@Override
	public Object dequeue() {
		if (this.isEmpty()) {
			return null;
		}
		Object ret = this.datas[this.head];
		this.head = this.indexPlus(this.head);
		return ret;
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append(getClass().getSimpleName()).append(" [");
		// [head, tail) 或者
		if (!this.isEmpty()) {
			int j = (this.head < this.tail) ? this.tail : this.tail
					+ getPresetLength();
			for (int i = this.head; i < j; i++) {
				int fixedIndex = this.fixedIndex(i);
				stringBuilder.append(this.datas[fixedIndex]);
				if (this.fixedIndex(fixedIndex + 1) == this.tail) {
					continue;
				}
				stringBuilder.append(", ");
			}
		}
		stringBuilder.append(']');
		return stringBuilder.toString();
	}

	public static void main(String[] args) {
		IQueue queue = new CircleQueue(3);
		System.out.println("-----enqueue-----");
		System.out.println(queue.enqueue(1));
		System.out.println(queue.enqueue(2));
		System.out.println(queue.enqueue(3));
		System.out.println(queue.enqueue(4));
		System.out.println(queue);

		System.out.println("-----dequeue-----");
		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println("-----dequeue-----");
		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println("-----enqueue-----");
		System.out.println(queue.enqueue(5));
		System.out.println(queue);

		System.out.println("-----enqueue-----");
		System.out.println(queue.enqueue(6));
		System.out.println(queue);

		System.out.println("-----dequeue-----");
		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println("-----dequeue-----");
		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println("-----dequeue-----");
		System.out.println(queue.dequeue());
		System.out.println(queue);
	}
}
